# !/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===========================
@Time : 2022/11/12 0012 12:09
@Author : 测试开发工程师
@File : 3. 列表排序.py
@Software: PyCharm
============================
"""

"""
什么是列表排序：
    将一组 "无序" 的记录序列调整为 "有序" 的记录序列
    列表排序：将无序列表 变为 有序列表
    输入： 列表
    输出： 有序列表
    升序 与 降序
    内置排序函数 ： sort()
        
常见排序算法介绍：
    排序 Low B 三人组： 冒泡排序 选择排序  插入排序
    排序 NB 三人组 ：   快速排序  堆栈排序  归并排序
    其他排序： 希尔排序  计数排序  基数排序
    
排序算法分析：
    
    冒泡排序：  目的：生成一个升序的列表
        列表每两个相邻的数，如果前面比后面大，则交换这两个数。
        一趟排序完成后，则无序区减少一个数，有序区增加一个数。
        代码关键点： 趟，无序区范围
    
    选择排序：
        一趟排序记录最小的数，放到第一个位置
        再一趟排序记录列表无序区最小的数，放到第二个位置
        算法关键点：有序区 和 无序区，无序区最小数的位置
        
    
        

"""
import random


# 冒泡排序   时间复杂度 O(n^2)
def bubble_sort(li):
    for i in range(len(li) - 1):  # i 表示 第 i 趟
        exchange = False
        for j in range(len(li) - i - 1):  # 每一趟的 指针位置
            if li[j] > li[j + 1]:  # 降序排列  改成 <
                li[j], li[j + 1] = li[j + 1], li[j]  # 交换
                exchange = True
        # print(li)
        if not exchange:
            return


li = [random.randint(0, 10000) for i in range(1000)]
print(li)
bubble_sort(li)
print(li)

# 校验。优化后 有  exchange 标记位
li = [1, 2, 3, 4, 5, 6, 7, 8, 9]
bubble_sort(li)
print(li)


# 选择排序。不推荐使用（两个列表，占内存）
def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new


li = [3, 2, 4, 1, 5, 6, 8, 7, 9]
print(select_sort_simple(li))


# 选择排序   时间复杂度 O(n^2)
def select_sort(li):
    for i in range(len(li) - 1):  # i 是第几趟
        min_loc = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


li = [3, 2, 4, 1, 5, 6, 8, 7, 9]
select_sort(li)
print(li)
